package com.zdb.algorithm.chessboard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class HorseChessboard {

    public static void main(String[] args) {
        Chessboard chessboard = new Chessboard(6, 6);

        chessboard.horseRun(new Point(0, 0), 1);
        System.out.println("失败次数：" + chessboard.failStep);
        if (chessboard.isFinished()) {
            System.out.println("--- 成功 ----");
            chessboard.print();
        } else {
            // 该位置无法走完
            System.out.println("--- 失败 ----");
            chessboard.print();
        }
    }

}

class Chessboard {

    // 行数
    private int col;
    // 列数
    private int row;
    // 用二位数组模拟棋盘， 0：表示没有走过，大于0的值代表的是第几步走当前位置
    private int[][] chessboard;

    private int size;

    private boolean finished;

    public long failStep = 0;

    public Chessboard(int col, int row) {
        this.col = col;
        this.row = row;
        size = col * row;
        chessboard = new int[row][col];
    }

    public boolean isFinished() {
        return finished;
    }

    /**
     * 马儿走下一步
     *
     * @param currentPoint 当前马儿棋子的位置
     * @param step         currentPoint 当前马儿棋子走的步数， nextPoint的步数为step+1
     */
    public void horseRun(Point currentPoint, int step) {
        // 冗余的，只是为了方便第一次调用该方法
        chessboard[currentPoint.row][currentPoint.col] = step;

        // 获取currentPoint在当前棋盘上能走的位置
        List<Point> nextPointList = next(currentPoint);

        sort(nextPointList);

        // 判断当前这一步是否还有位子可以走，如果没有位子，需要回溯
        // 递归退出条件：
        // 1. step == 棋盘大小-1 && 可以走的位置为1，说明走完这一步棋盘成功走完
        // 2. step < 棋盘大小-1 && 没有位置可以走，
        //    说明currentPoint这一步之后无路可走，且棋盘没有走完，失败了
        //    需要回溯，将currentPoint设置为未走过，找其他位置走
        if (step + 1 == size && nextPointList.size() == 1) {
            chessboard[nextPointList.get(0).row][nextPointList.get(0).col] = step + 1;
            finished = true;
            return;
        } else if (step + 1 < size && nextPointList.size() == 0) {
            // 无路可走了
            failStep += step;
            System.out.println("------ 尝试失败 --------" + step);
            return;
        }

        // 循环获取遍历可以走的位置，进入下一步
        for (int i = 0; i < nextPointList.size(); i++) {
            Point nextPoint = nextPointList.get(i);

            if (chessboard[nextPoint.row][nextPoint.col] != 0) {
                System.err.println("------ error --------" + nextPoint);
            }
            chessboard[nextPoint.row][nextPoint.col] = step + 1;
            horseRun(nextPoint, step + 1);
            if (finished) {
                break;
            } else {
                // 说明nextPoint这一步没有能走完棋盘，撤回这一步
                chessboard[nextPoint.row][nextPoint.col] = 0;
            }
        }

    }

    /**
     * 寻找当前位置可以走的点, 最多8个点
     *
     * @param cp
     * @return
     */
    private List<Point> next(Point cp) {
        List<Point> pointList = new ArrayList<>();

        Point p = new Point(0, 0);
        // 5
        if ((p.col = cp.col - 2) >= 0 && (p.row = cp.row - 1) >= 0) {
            pointList.add(new Point(p));
        }

        // 6
        if ((p.col = cp.col - 1) >= 0 && (p.row = cp.row - 2) >= 0) {
            pointList.add(new Point(p));
        }

        // 7
        if ((p.col = cp.col + 1) < col && (p.row = cp.row - 2) >= 0) {
            pointList.add(new Point(p));
        }

        // 0
        if ((p.col = cp.col + 2) < col && (p.row = cp.row - 1) >= 0) {
            pointList.add(new Point(p));
        }

        // 1
        if ((p.col = cp.col + 2) < col && (p.row = cp.row + 1) < row) {
            pointList.add(new Point(p));
        }

        // 2
        if ((p.col = cp.col + 1) < col && (p.row = cp.row + 2) < row) {
            pointList.add(new Point(p));
        }

        // 3
        if ((p.col = cp.col - 1) >= 0 && (p.row = cp.row + 2) < row) {
            pointList.add(new Point(p));
        }

        // 4
        if ((p.col = cp.col - 2) >= 0 && (p.row = cp.row + 1) < row) {
            pointList.add(new Point(p));
        }

        return pointList.stream().filter(
                (Point point) -> chessboard[point.row][point.col] == 0
        ).collect(Collectors.toList());
    }

    public void sort(List<Point> pointList) {
        pointList.forEach((Point point) -> {
            point.nextCnt = next(point).size();
        });
        pointList.sort(new Comparator<Point>() {
            @Override public int compare(Point o1, Point o2) {
                return o1.nextCnt - o2.nextCnt;
            }
        });
    }

    public void print() {
        for (int i = 0; i < chessboard.length; i++) {
            System.out.println(Arrays.toString(chessboard[i]));
        }
    }

}

class Point {

    public int col;
    public int row;

    // 当前点的下一步走的位置
    public int nextCnt;

    public Point(int col, int row) {
        this.col = col;
        this.row = row;
    }

    public Point(Point point) {
        this.col = point.col;
        this.row = point.row;
    }

    public int getNextCnt() {
        return nextCnt;
    }

    public void setNextCnt(int nextCnt) {
        this.nextCnt = nextCnt;
    }

    @Override public String toString() {
        return "Point{" +
                "col=" + col +
                ", row=" + row +
                '}';
    }
}
